package com.lw.leetcode.tree.b;


/**
 * Created with IntelliJ IDEA.
 * <p>
 * tree
 * 677. 键值映射
 * 剑指 Offer II 066. 单词之和
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/2 15:06
 */
public class MapSum {

    public static void main(String[] args) {
        MapSum test = new MapSum();
        // [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]  [null, null, 3, null, 5]
        test.insert("apple", 3);
        System.out.println(test.sum("ap"));
        test.insert("app", 4);
        System.out.println(test.sum("ap"));
        test.insert("ap", 5);
        System.out.println(test.sum("ap"));

        //[[], ["a",3], ["ap"], ["b",2], ["a"]] [null,null,0,null,3]

        test.insert("a", 3);
        System.out.println(test.sum("ap"));
        test.insert("b", 2);
        System.out.println(test.sum("a"));
    }

    private TreeNode nodes;

    public MapSum() {
        nodes = new TreeNode();
    }

    public void insert(String key, int val) {
        find(key.toCharArray(), 0, nodes, val);
    }

    private void find(char[] chars, int index, TreeNode node, int val) {
        char c = chars[index];
        TreeNode[] child = node.child;
        TreeNode item = child[c - 'a'];
        if (item == null) {
            item = new TreeNode(c);
            child[c - 'a'] = item;
        }
        if (index + 1 == chars.length) {
            item.val = val;
        } else {
            find(chars, index + 1, item, val);
        }
    }

    public int sum(String prefix) {
        char[] chars = prefix.toCharArray();
        return find(chars, 0, nodes);
    }

    private int find(char[] chars, int index, TreeNode node) {

        if (index + 1 > chars.length) {
            int sum = 0;
            for (TreeNode item : node.child) {
                if (item != null) {
                    sum += item.val;
                    sum += find(chars, index + 1, item);
                }
            }
            return sum;
        } else {
            char c = chars[index];
            TreeNode[] child = node.child;
            TreeNode item = child[c - 'a'];
            if (item == null) {
                return 0;
            } else {
                if (index + 1 == chars.length) {
                    return item.val + find(chars, index + 1, item);
                } else {
                    return find(chars, index + 1, item);
                }

            }
        }
    }

    private static class TreeNode {
        public char key;
        public int val;
        public TreeNode[] child;

        TreeNode() {
            child = new TreeNode[26];
        }

        public TreeNode(char key) {
            this.key = key;
            child = new TreeNode[26];
        }
    }

}
